Понятная информатика,

Для передачи, обработки и хранения информации необходимо ее зафиксировать с помощью определенной знаковой системы (алфавита), т. е. закодировать.

Кодирование – это процесс представления информации в виде последовательности условных обозначений. Декодирование – это процесс, обратный кодированию..

Кодирование информации всегда происходит по определенным правилам. Правило кодирования называется кодом.

Последовательность символов известной длины из конечного набора знаков (алфавита) используемых для кодирования, называется  кодовым словом (например, кодовое слово для буквы «O» в азбуке Морзе имеет длину равную трем и представляет последовательность из трех символов тире «— — —»).

 

Способы кодирования информации зависят от конкретной задачи.  

 

Для решения таких задач полезно знать и использовать условия Фано, выполнение  которых  служит достаточными для однозначного декодирования заданного сообщения, то есть перебора различных вариантов при декодировании не потребуется. Это позволяет избежать ошибок и сэкономить время для решения задачи.

Прямое условие Фано гласит, что ни одно кодовое слово не может служить началом другого кодового слова.

Обратное условие Фано гласит, что ни одно кодовое слово не может служить концом другого кодового слова.

 

Например, в кодовых словах  01, 011, 010, 110, 100  нарушено  прямое условие Фано, так как кодовое слово 01 является началом кодового слова 011. Обратное условие не нарушено, поэтому задачу по раскодированию с такими кодовыми словами рекомендуется решать с конца сообщения, что обеспечит его однозначное декодирование.

В кодовых словах 01, 001, 100, 101, 110 нарушено обратное условие Фано, так как кодовое слово 01 является концом кодовых слов 001 и 101. Прямое условие не нарушено, поэтому задачу с такими заданными кодовыми словами для однозначного декодирования рекомендуется решать с начала сообщения.

В кодовых словах 01, 001, 010, 100, 110 нарушены оба условия Фано, так как кодовое слово 01 служит началом кодового слова 010 и концом кодового слова 001. Тогда при решении такой задачи однозначное декодирование невозможно, решать можно с любой стороны – все равно придется перебирать варианты.

 

Часто при решении задач по декодированию достаточно умения логически мыслить, быть внимательным и аккуратным – и все получится!

 

Следует учитывать, что результатом декодирования не обязательно должно быть осмысленное слово!

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

 

Задача 1.

 

На киностудии снимали фильм про шпионов и закодировали сообщение придуманным шифром. В сообщении присутствуют только буквы приведённого фрагмента кодовой таблицы:

Б        И       С       Е       Р

110     01     010   111    011

Определите, какое сообщение закодировано в строчке:

01111111001

В ответе запишите последовательность букв без запятых и других знаков препинания.

 

Решение.

В исходных кодовых словах данной задачи нарушено прямое условие Фано (кодовое слово 01 является началом кодовых слов 010 и 011), то для однозначного решения задачи будем декодировать сообщение с конца:

Ответ: РЕБИ

 

Задача 2.

 

На киностудии снимали фильм про шпионов и закодировали сообщение придуманным шифром. В сообщении присутствуют только буквы приведённого фрагмента кодовой таблицы:

М      Е      Т      Л      А

01  100  110   101    111

Определите, какое сообщение закодировано в строчке:

11010001111.

В ответе запишите последовательность букв без запятых и других знаков препинания.

 

Решение.

В исходных кодовых словах данной задачи нарушено обратное условие Фано (кодовое слово 10 является началом кодовых слов 010 и 110), то для однозначного решения задачи будем декодировать сообщение с конца:

Ответ: ТЕМА

 

Задача 3.

Агент 007, передавая важные сведения своему напарнику, закодировал сообщение придуманным шифром. В сообщении присутствуют только буквы из приведённого фрагмента кодовой таблицы:

Р       Ы         Б      К       А

€ ?   ? ? €    ? ?    ? €    ? € ?

Определите, какое сообщение закодировано в строчке:

? ? ? ? € ? €.

В ответе запишите последовательность букв без запятых и других знаков препинания.

 

Решение.

Так как кодовое слово ? ?  является началом кодового слова? ? €, а кодовое слово   € ? является концом кодового слова ? € ?, то однозначного декодирования в данной задаче невозможно. Тогда, перебирая варианты, получаем слово БЫК.

Ответ: БЫК

 

Задача 4.

Кирилл шифрует английские слова, записывая вместо каждой буквы её номер в алфавите (без пробелов). Номера букв даны в таблице:

А 1     K 11      U 21

B 2     L 12      V 22

C 3     M 13     W 23

D 4     N 14     X 24

E 5     O 15     Y 25

F 6     P 16      Z 26

G 7     Q 17     H 8

R 18    I 9        S 19

J 10    T 20      

Некоторые шифровки можно расшифровать не одним способом. Например, 16118 может означать «AFAR», может — «РАR», а может — «AFAAH». Даны четыре шифровки:

18205

20158

20518

81205

Только одна из них расшифровывается единственным способом. Найдите её и расшифруйте. То, что получилось, запишите в качестве ответа.

 

Решение.

В данной таблице нарушены оба условия Фано, но есть своя закономерность: все кодовые слова лежат в диапазоне от 1 до 26, то есть кодового слова 0 здесь нет.

Тогда однозначно расшифровывается только последняя из заданных шифровок, которая декодируется как НАTE.

Ответ: НАТЕ